function TreeNode(val = 0, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

// 值为null，表示空节点
function makeBinaryTreeFromArray(arr) {
  const len = arr.length;
  const createNode = (index) => {
    if (index < len && arr[index] != null) {
      return new TreeNode(
        arr[index],
        createNode(2 * index + 1),
        createNode(2 * index + 2)
      );
    }
    return null;
  };

  return createNode(0);
}

const Mirros = {
  preOrderTraversal(root) {
    if (root == null) {
      return;
    }

    let cur = root;
    while (cur) {
      let mostRight = cur.left;
      if (mostRight !== null) {
        while (mostRight.right != null && mostRight.right != cur) {
          mostRight = mostRight.right;
        }
        if (mostRight.right == null) {
          mostRight.right = cur;
          console.log(cur.val);
          cur = cur.left;
          continue;
        }

        mostRight.right = null;
      } else {
        console.log(cur.val);
      }
      cur = cur.right;
    }
  },

  inOrderTraversal(root) {
    if (root == null) {
      return;
    }

    let cur = root;
    while (cur) {
      let mostRight = cur.left;
      if (mostRight !== null) {
        while (mostRight.right != null && mostRight.right != cur) {
          mostRight = mostRight.right;
        }
        if (mostRight.right == null) {
          mostRight.right = cur;
          cur = cur.left;
          continue;
        }

        mostRight.right = null;
      }
      console.log(cur.val);
      cur = cur.right;
    }
  },

  postOrderTraversal(root) {
    if (root == null) {
      return;
    }

    let cur = root;
    while (cur) {
      if (cur.left) {
        let mostRight = cur.left;
        while (mostRight.right != null && mostRight.right != cur) {
          mostRight = mostRight.right;
        }

        if (mostRight.right == null) {
          mostRight.right = cur;
          cur = cur.left;
          continue;
        } else {
          mostRight.right = null;
          this._printEdge(cur.left);
        }
      }
      cur = cur.right;
    }
    this._printEdge(root);
  },
  _printEdge(node) {
    let tail = this._reverseRightEdge(node); // reverse for print

    let cur = tail;
    while (cur) {
      console.log(cur.val);
      cur = cur.right;
    }

    this._reverseRightEdge(tail); // resume
  },
  _reverseRightEdge(node) {
    let pre = null;
    while (node) {
      let _cur_right = node.right;
      // reverse
      node.right = pre;
      // iteration
      pre = node;
      node = _cur_right;
    }
    return pre;
  },
};

const recursive = {
  preOrderTraversal(root) {
    if (root) {
      console.log(root.val);
      if (root.left) this.preOrderTraversal(root.left);
      if (root.right) this.preOrderTraversal(root.right);
    }
  },
  inOrderTraversal(root) {
    if (root) {
      if (root.left) this.inOrderTraversal(root.left);
      console.log(root.val);
      if (root.right) this.inOrderTraversal(root.right);
    }
  },
  postOrderTraversal(root) {
    if (root) {
      if (root.left) this.postOrderTraversal(root.left);
      if (root.right) this.postOrderTraversal(root.right);
      console.log(root.val);
    }
  },
};

const iteration = {
  preOrderTraversal(root) {
    let stack = [];
    root && stack.push(root);

    let node;
    while (stack.length > 0) {
      node = stack.pop();
      console.log(node.val);
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  },
  preOrderTraversal_template(root) {
    let stack = [];

    let node = root;
    while (stack.length > 0 || node != null) {
      while (node) {
        console.log(node.val);
        stack.push(node);
        node = node.left;
      }
      node = stack.pop();
      node = node.right;
    }
  },

  inOrderTraversal(root) {
    let stack = [];

    let node = root;
    while (stack.length > 0 || node != null) {
      while (node) {
        stack.push(node);
        node = node.left;
      }
      node = stack.pop();
      console.log(node.val);
      node = node.right;
    }
  },

  /**
   * find the most left.
   * visit the root and right.
   * if has right, push back root, enter right
   * if right visited, visit root
   * if no right, visit root
   * when visit root, it is some node's right, so record it.
   * has curNode, push curNode
   * no curNode, pop stack
   */
  postOrderTraversal(root) {
    let stack = [];

    let curNode = root;
    let visitedRight = null;
    while (stack.length > 0 || curNode != null) {
      while (curNode) {
        stack.push(curNode);
        curNode = curNode.left;
      }
      curNode = stack.pop();
      if (curNode.right == null || curNode.right == visitedRight) {
        console.log(curNode.val);
        visitedRight = curNode;
        curNode = null;
      } else {
        stack.push(curNode);
        curNode = curNode.right;
      }
    }
  },
};

function levelOrderTraversal(root) {
  let queue = [];
  let cur = root;
  while (queue.length > 0 || cur) {
    console.log(cur.val);
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
    cur = queue.shift();
  }
}

function levelOrderTraversal_withLevel(root) {
  let queue = [root];
  while (queue.length > 0) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      let cur = queue.shift();
      if (cur.left) queue.push(cur.left);
      if (cur.right) queue.push(cur.right);
      console.log(cur.val);
    }
    if (queue.length > 0) {
      console.log("|");
    }
  }
}
